package sort.leetcode;

/**
 * @Description: 数组中的逆序对
 * @Author Stark
 * @Date 2022/3/20 10:43
 **/
public class Num51_ReversePairs {
    public static int reversePairs(int[] nums) {
        int[] temp = new int[nums.length];//额外的辅助空间
        return mergeSort(nums, 0, nums.length - 1, temp);
    }

    //使用归并排序对数组进行排序，在排序的过程中就可把逆序对数求出
    private static int mergeSort(int[] arr, int left, int right, int[] temp) {
        if(left >= right){
            return 0;
        }
        int mid = left + ((right - left) >> 1);
        int sum1 = mergeSort(arr,left,mid,temp);
        int sum2 = mergeSort(arr,mid + 1,right,temp);
        if(arr[mid] > arr[mid + 1]) {
            return merge(arr, left, mid, right, temp) + sum1 + sum2;
        }
        return sum1 + sum2;
    }

    private static int merge(int[] arr, int left,int mid, int right, int[] temp) {
        int l1 = left;
        int l2 = mid + 1;
        int index = left;
        int sum = 0;
        while(l1 <= mid && l2 <= right){
            if(arr[l1] <= arr[l2]){
                //当左区间的数<=右区间的数时,将其排序,索引往后走
                //比较剩下的数
                temp[index++] = arr[l1++];
            }else{
                //当左区间的某个数大于右区间某个数时
                //sum加上左区间剩下未排序的数,因为升序,左区间后面的数都可与右区间那个数构成逆序对
                sum += mid - l1 + 1;
                temp[index++] = arr[l2++];
            }
        }
        while(l1 <= mid){
            temp[index++] = arr[l1++];
        }
        while(l2 <= right){
            temp[index++] = arr[l2++];
        }
        for (int i = left; i <= right; i++) {
            arr[i] = temp[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] nums = {6,4,6,4};
        int ret = reversePairs(nums);
        System.out.println(ret);
    }
}
